翻訳と辞書 Words near each other ・ Y-chromosome haplogroups by populations ・ Y-class lifeboat ・ Y-DNA haplogroups by ethnic group ・ Y-DNA haplogroups by populations of East and Southeast Asia ・ Y-DNA haplogroups by populations of Near East ・ Y-DNA haplogroups by populations of North Africa ・ Y-DNA haplogroups by populations of Sub-Saharan Africa ・ Y-DNA haplogroups by populations of the Caucasus ・ Y-DNA haplogroups in Central and North Asian populations ・ Y-DNA haplogroups in European populations ・ Y-DNA haplogroups in indigenous peoples of the Americas ・ Y-DNA haplogroups in Oceanian populations ・ Y-DNA haplogroups in South Asian populations ・ Y-factor ・ Y-Factor Cyprus (Season 1) ・ Y-fast trie ・ Y-Films ・ Y-homeomorphism ・ Y-intercept ・ Y-Love ・ Y-Mag ・ Y-matrix ・ Y-ME National Breast Cancer Organization ・ Y-O Ranch, Wyoming ・ Y-O-U ・ Y-O-U (album) ・ Y-patterned moray eel ・ Y-Set (intravenous therapy) ・ Y-SNP ・ Y-stations Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Y-fast trie ： ウィキペディア英語版 Y-fast trie In computer science, a y-fast trie is a data structure for storing integers from a bounded domain. It supports exact and predecessor or successor queries in time ''O''(log log ''M''), using ''O''(''n'') space, where ''n'' is the number of stored values and ''M'' is the maximum value in the domain. The structure was proposed by Dan Willard in 1982〔 to decrease the ''O''(''n'' log ''M'') space used by an x-fast trie. ==Structure== A y-fast trie consists of two data structures: the top half is an x-fast trie and the lower half consists of a number of balanced binary trees. The keys are divided into groups of ''O''(log ''M'') consecutive elements and for each group a balanced binary search tree is created. To facilitate efficient insertion and deletion, each group contains at least (log ''M'')/4 and at most 2 log ''M'' elements.〔 For each balanced binary search tree a representative ''r'' is chosen. These representatives are stored in the x-fast trie. A representative ''r'' need not to be an element of the tree associated with it, but it does need be an integer smaller than the successor of ''r'' and the minimum element of the tree associated with that successor and greater than the predecessor of ''r'' and the maximum element of the tree associated with that predecessor. Initially, the representative of a tree will be an integer between the minimum and maximum element in its tree. Since the x-fast trie stores ''O''(''n'' / log ''M'') representatives and each representative occurs in ''O''(log ''M'') hash tables, this part of the y-fast trie uses ''O''(''n'') space. The balanced binary search trees store ''n'' elements in total which uses ''O''(''n'') space. Hence, in total a y-fast trie uses ''O''(''n'') space. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Y-fast trie」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.